package 优先算法.滑动窗口.最小覆盖子串;

import java.util.Arrays;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Solution so =new Solution();
        String s = "a";
        String t = "aa";
        String rel = so.minWindow(s, t);
        System.out.println(rel);
    }

}
class Solution {//优化

    public String minWindow(String s, String t) {
        int[] hash1 = new int[58];
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int kind = 0;
        for(char c : tt){
            if(hash1[c-'A'] == 0){
                kind++;
            }
            hash1[c-'A']++;
        }
        int[] hash2 = new int[58];
        int left = 0,right =0,MinLeft = -1,len = Integer.MAX_VALUE,count = 0;
        while(right < ss.length){
            //进窗口
            char in = ss[right++];

            hash2[in-'A']++;
            if(hash2[in-'A'] == hash1[in-'A']){
                count++;
            }

            while(count == kind){
                if(right - left < len){
                    len = right -left;
                    MinLeft = left;
                }
                char out = ss[left++];
                if(hash1[out-'A'] == hash2[out-'A']){
                    count--;
                }
                hash2[out-'A']--;
            }
        }
        if(MinLeft == -1){
            return new String();
        }else{
            return s.substring(MinLeft, MinLeft+len);
        }
    }
}
class Solution1 {
    public static boolean isOk(HashMap<Character,Integer>hash1, HashMap<Character,Integer>hash2){
        for(Character c : hash1.keySet()){
            if(hash1.get(c) > hash2.getOrDefault(c,0)){
                return false;
            }
        }
        return true;
    }
    public String minWindow(String s, String t) {
        String rel ="";
        if(t.length() > s.length()){
            return rel;
        }
        HashMap<Character,Integer> hash1 = new HashMap<>();

        char[] tt = t.toCharArray();
        for(char c : tt){
            hash1.put(c,hash1.getOrDefault(c,0)+1);
        }

        char[] ss = s.toCharArray();
        HashMap<Character,Integer> hash2 = new HashMap<>();
        int left = 0,right =0,minLeft = 0,len =Integer.MAX_VALUE,lastLen;
        int n = ss.length;
        while(right < n){
            //进窗口
            char in = ss[right++];
            hash2.put(in,hash2.getOrDefault(in,0)+1);
            while(isOk(hash1,hash2)){
                lastLen =len;
                len = Math.min(len,right - left);
                if(lastLen != len){
                    minLeft = left;
                }
                char out = ss[left++];
                hash2.put(out,hash2.get(out)-1);
            }
        }
        if(len == Integer.MAX_VALUE){
            return rel;
        }
         rel = s.substring(minLeft,len+minLeft);
        return  rel;
    }
}